public class LeetCode279 {
    public int numSquares(int n) {
        // 创建一个数组 dp，其中 dp[i] 表示数字 i 可以由多少个完全平方数相加得到的最小数量。
        int[] dp = new int[n + 1];

        // 遍历从 1 到 n 的所有数字来填充 dp 数组。
        for (int i = 1; i <= n; i++) {
            // 对于每个 i，我们初始化 minn 为一个很大的数（这里使用 Integer.MAX_VALUE），用于保存当前找到的最小组合数量。
            int minn = Integer.MAX_VALUE;

            // 尝试用所有的完全平方数 j*j 来更新 dp[i]，这里的 j*j 必须小于等于 i。
            for (int j = 1; j * j <= i; j++) {
                // 我们检查将 j*j 从 i 中减去后剩下的数 dp[i - j * j] 的最优解，
                // 然后加1（因为我们使用了一个 j*j），并与当前的 minn 比较，取较小值。
                minn = Math.min(minn, dp[i - j * j] + 1);
            }
            // 更新 dp[i] 为找到的最小组合数量。
            dp[i] = minn;
        }
        // 最终返回 dp[n]，即为 n 的答案。
        return dp[n];
    }
}
